package cn.cxq.learning.dynamic_programming;

/**
 * 01背包
 */
public class KnapsackProblem {

    private int[] weight; //物品所需空间

    private int[] value; //物品价值

    private int knapsackSize; //背包容量

    private int[][] v; //各个情况下的最大值，行表示物品种类，列表示背包容量

    private int[][] path; //改变路径记录

    public KnapsackProblem(int[] weight, int[] value, int knapsackSize) {
        this.weight = weight;
        this.value = value;
        this.knapsackSize = knapsackSize;

        this.v = new int[this.weight.length + 1][this.knapsackSize + 1];
        for (int i = 0; i < this.v.length; i++) {
            this.v[i][0] = 0;
            this.v[0][i] = 0;
        }

        this.path = new int[this.weight.length + 1][this.knapsackSize + 1];
        for (int i = 0; i < this.path.length; i++) {
            this.path[i][0] = 0;
            this.path[0][i] = 0;
        }
    }

    public void solve() {

        for (int i = 1; i <= this.weight.length; i++) {
            for (int j = 1; j <= this.knapsackSize; j++) {
                //如果装不下，根本不需要考虑将其装入，直接取 容量一致且没有该商品的最大价值 作为该情况下的最大值。
                if (weight[i - 1] > j) {
                    v[i][j] = v[i - 1][j];
                } else {
                    //如果装的下，那就腾出空间给新来的物品，对比一下 容量一致且没有该商品的最大价值 和 腾出空间将其放入的价值和剩余空间的最大值之和 哪个大，作为该情况下的最大值。
//                    v[i][j] = Math.max(v[i-1][j],value[i-1] + v[i-1][j-weight[i-1]]);
                    if (v[i - 1][j] > value[i - 1] + v[i - 1][j - weight[i - 1]]) {
                        v[i][j] = v[i - 1][j];
                    } else {
                        v[i][j] = value[i - 1] + v[i - 1][j - weight[i - 1]];
                        path[i][j] = 1;
                    }
                }
            }
        }
    }

    public void printV() {
        System.out.println("各个子情况下的最大值：");
        printArray(this.v);
        System.out.println("最大值：" + this.v[this.weight.length][this.knapsackSize]);
    }

    public void printPath() {
        System.out.println("路径跟踪：");
        printArray(this.path);
        System.out.println("跟踪结果：");

        int i = path.length - 1;
        int j = path[0].length - 1;

        while (i > 0 && j > 0) {

            if (path[i][j] == 1) {
                System.out.println("第" + String.format("%2d", i) + " 件物品放入背包；");
                j -= weight[i - 1];
            }

            i--;
        }
    }

    private void printArray(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                System.out.print(String.format("%7d", arr[i][j]) + " ");
            }
            System.out.println();
        }
    }
}
